<?php
//堆排序算法
//打印二叉树
function heap_tree($arr, $unit_width=2){
	array_unshift($arr, 0);
	$lenght = count($arr);
	$depth = ceil(log($lenght, 2));
	$start = 1;
	for($i=$depth;$i>=1;$i--){
		$pre = 2 ** ($i - 1) -1;
		echo str_repeat('_', $pre * $unit_width);
		$end = 2 * $start;
		for($j = $start; $j < $end; $j++){
			echo $arr[$j];
			// echo $j;
			if($j < $end - 1 && $j < $lenght - 1){
				echo str_repeat('_', (2 * $pre + 1) * $unit_width);
			}
		}
		echo "<br><br>";
		$start = $end;
	}
}

// 把array中前n个元素的第i个节点（及其子节点）修正为大堆顶
function heap_adjust($i, $n, &$arr){
	array_unshift($arr, 0);
	while(2 * $i <= $n){
		$lchild_index = 2 * $i;
		$max_child_index = $lchild_index; //先假设左节点最大
		if($lchild_index + 1 <= $n && $arr[$lchild_index + 1] > $arr[$lchild_index]){
			$max_child_index = $lchild_index + 1; //存在右节点，并且右节点最大
		}
		//已经得出最大节点了，接下来和自己的根比较
		if($arr[$max_child_index] > $arr[$i]){
			$temp = $arr[$i];
			$arr[$i] = $arr[$max_child_index];
			$arr[$max_child_index] = $temp;
			$i = $max_child_index;
		}else{
			break;
		}
	}
	array_shift($arr);
}

//堆排序：先得到纯大顶堆，然后循环排序。需要heap_adjust()发放支持
function heap_sort($arr){
	//从$n/2开始到1， 逐个修正为大堆顶
	$n = count($arr);
	for($i=floor($n/2);$i>0;$i--){
		heap_adjust($i, $n, $arr);
		echo "修正节点".$i."：------------- 查看变化 -------------<br>";
		heap_tree($arr);
	}
	echo "得到纯大顶堆：--------------------------<br>";
	heap_tree($arr);
	
	//循环排序，每次得到纯大顶堆后，把根换到有序区
	// array_unshift($arr, 0);
	for($m=$n-1;$m>=1;$m--){
		$temp = $arr[0];
		$arr[0] = $arr[$m];
		$arr[$m] = $temp;
		heap_adjust(1, $m, $arr);
		// echo "循环排序，换到有序区的值：".$arr[$m]."---------- 查看变化 ----------<br>";
		// heap_tree($arr);
	}
	return $arr;
}

$arr = [30, 20, 80, 40, 50, 10, 60, 70, 90,22];
$arr = [45, 48, 74, 58, 96, 21, 45, 88, 75, 36, 95, 84, 15];

echo "原始数据：--------------------------<br>";
heap_tree($arr);

// echo "修正指定节点：--------------------------<br>";
// heap_adjust(4, 9, $arr);
// heap_adjust(2, 10, $arr);
// heap_tree($arr);

echo "堆排序：--------------------------<br>";
$arr_sort = heap_sort($arr);
echo "<pre>";
print_r($arr_sort);
echo "</pre>";



?>